MIME-Version: 1.0
Server: CERN/3.0
Date: Wednesday, 20-Nov-96 19:47:40 GMT
Content-Type: text/html
Content-Length: 4512
Last-Modified: Friday, 30-Aug-96 02:28:56 GMT

<html>
<head> <title> David Pearson </title> </head>
<body>
<img src="pearson.gif">
<p>
<h1> David Pearson </h1>

<h3> Research Interests </h3>

My thesis investigates highly scalable parallel computers consisting
of very simple processors connected in a 3-dimensional mesh.
The guiding vision of this work is of a time, perhaps 50 years hence,
in which materials science has taken the place of computer architecture,
and computers are crystals, with each processor a molecule in the lattice.
Long before this goal can be realized, we can and should prepare for the
ubiquitous parallelism it will offer.  Our algorithms must heed the laws
of physics and pay attention, as chip designers do now, to spatial layout
and the (currently hidden) cost of communication.  This can be accomplished
by designing our algorithms for a 3-D mesh.
<p>
To pursue this vision requires both theoretical and practical work.
So far, my work could be characterized as a feasibility study: I
have produced a 3-D cellular architecture which could
be efficiently realized with current hardware, a simulator for this
architecture, algorithms, programs, and an operating system design
for general-purpose computing.
(I believe that general-purpose computers, not problems like protein
structure, are the grand challenge of parallel architecture.  Parallel
computational power will not really succeed until it becomes a commodity
and is sold for desktop machines or video games.)
<p>
Directions for future research include VLSI implementation of this architecture
and the design of a programming language.  Most widely-used languages hide
the details of the machine's instruction set, but reflect the underlying
Von Neumann architecture.  I believe that this connection to the architecture
has been a good thing for algorithm design, and to really exploit parallel
machines we need a language for which the costs of operations are as easy
to estimate as they are for C++ on a Von Neumann machine.

<h3> Publications </h3>

<ul>
<li> S. D. Dunten, D. S. Pearson, and W. Y. Arms. ``The Kiewit Network: A
     High-Speed Campus Network''. In <i> 25th IEEE Computer Society
     International Conference </i> (IEEE COMPCON), pp. 247-254, (Fall 1982).
<li> D. Pearson, S. U. Pillai, and Y. Lee. ``An Algorithm for Near-Optimal
     Placement of Sensor Elements''. <i> IEEE Transactions on Information
     Theory </i> <b> 36, </b> pp. 1280-1284 (1990).
<li> D. Pearson and V. Vazirani. ``A Fast Parallel Algorithm for Finding a
     Maximal Bipartite Set''. In <i> Foundations of Software Technology
     and Theoretical Computer Science </i> 10 (FST&TCS), pp. 225-231,
     (1990). Published as <i> Lecture Notes in Computer Science </i>
     <b> 472. </b>
<li> D. Pearson and V. Vazirani. ``<a href=mbs.ps>Efficient Sequential and
     Parallel Algorithms for Maximal Bipartite Sets</a>''. <i> Journal of
     Algorithms </i> <b> 14, </b> pp. 171-179 (1993).
<li> R. Johnson, D. Pearson, and K. Pingali. ``Finding Regions Fast:
     Single Entry Single Exit and Control Regions in Linear Time''.
     Cornell CS Tech. Report 93-1365.
<li> R. Johnson, D. Pearson, and K. Pingali. ``The program structure tree:
     Computing control regions in linear time''. In <i> Proceedings of the
     Sigplan '94 Conference on Programming Language Design and Implementation
     </i> (PLDI), pp. 171-185, (1994).  Published as <i> ACM SIGPLAN Notices
     </i> <b> 29</b>(6).
<li> D. Pearson. ``<a href=change.ps>A Polynomial-time Algorithm for the
     Change-Making Problem</a>'', Cornell CS Tech. Report 94-1433.
<li> B. Hao and D. Pearson. ``Instruction Scheduling and Global Register
     Allocation for SIMD Multiprocessors''. In <i> International Workshop on
     Parallel Algorithms for Irregularly Structured Problems </i>
     (Irregular 95), pp. 81-86, Sept. 1995.
     Published as <i> Lecture Notes in Computer Science </i> <b> 980. </b>
<li> B. Hao, D. Pearson, and R. Zippel. ``Global Register Allocation for SIMD
     Multiprocessors''. <i> Journal of Computer Science and Technology, </i>
     Jan. 1996, Allerton Press.
<li> D. Pearson. ``<a href=rsa.ps>A Parallel Implementation of RSA</a>''.
     in <i> Selected Areas in Cryptography </i> (SAC), Aug. 1996 (to appear).
</ul>

<hr>

<address>
Computer Science Department<br>
5133 Upson Hall<br>
Cornell University<br>
Ithaca, New York 14853-7501, USA<br>
</address>
<br>
Email: <kbd>pearson@cs.cornell.edu</kbd> <br>
Tel: (607) 255-9189 <br>
Fax: (607) 255-4428 <br>

</body>
</html>
